Theorem (time hierarchy)

If f,gf,g are time-constructible functions satisfying f(n)log⁡f(x)=o(g(n))f(n)\log f(x) = o(g(n)), then

DTIME⁡(f(n))⊊DTIME⁡(g(n))\operatorname{DTIME}(f(n)) \subsetneq \operatorname{DTIME}(g(n))

where time-constructible function ff means mapping x↦f(|x|)x \mapsto f(|x|) can be computed in O(f(n))O(f(n)) time.

(DTIME)

Proof

#incomplete

Theorem (non-deterministic time hierarchy)

If f,gf,g are time-constructible functions satisfying f(n+1)=o(g(n))f(n+1) = o(g(n)), then

NTIME⁡(f(n))⊊NTIME⁡(g(n))\operatorname{NTIME}(f(n)) \subsetneq \operatorname{NTIME}(g(n))

(NTIME)

Notes

  • DTIME(f(n)) means the class of functions that can be decided in time f(n)
  • so, it means set of functions that may be decided in time f(n) is a strict subset of those that may be decided in time g(n)
    • i.e., allowing TMs more computational time strictly increases the set of languages they can decide
  • (analogously for non-deterministic version)

See also

References

  1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, pp. 69-70.